<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<meta http-equiv="Content-Type" content="text/xhtml;charset=UTF-8"/>
<meta http-equiv="X-UA-Compatible" content="IE=9"/>
<title>Data Structures for Sets and Graphs: ColoringHeuristic&lt; T, D &gt; Class Template Reference</title>
<link href="tabs.css" rel="stylesheet" type="text/css"/>
<script type="text/javascript" src="jquery.js"></script>
<script type="text/javascript" src="dynsections.js"></script>
<link href="search/search.css" rel="stylesheet" type="text/css"/>
<script type="text/javascript" src="search/search.js"></script>
<script type="text/javascript">
  $(document).ready(function() { searchBox.OnSelectItem(0); });
</script>
<link href="doxygen.css" rel="stylesheet" type="text/css" />
</head>
<body>
<div id="top"><!-- do not remove this div, it is closed by doxygen! -->
<div id="titlearea">
<table cellspacing="0" cellpadding="0">
 <tbody>
 <tr style="height: 56px;">
  <td style="padding-left: 0.5em;">
   <div id="projectname">Data Structures for Sets and Graphs
   </div>
  </td>
 </tr>
 </tbody>
</table>
</div>
<!-- end header part -->
<!-- Generated by Doxygen 1.8.1.1 -->
<script type="text/javascript">
var searchBox = new SearchBox("searchBox", "search",false,'Search');
</script>
  <div id="navrow1" class="tabs">
    <ul class="tablist">
      <li><a href="index.html"><span>Main&#160;Page</span></a></li>
      <li><a href="namespaces.html"><span>Namespaces</span></a></li>
      <li class="current"><a href="annotated.html"><span>Classes</span></a></li>
      <li><a href="files.html"><span>Files</span></a></li>
      <li>
        <div id="MSearchBox" class="MSearchBoxInactive">
        <span class="left">
          <img id="MSearchSelect" src="search/mag_sel.png"
               onmouseover="return searchBox.OnSearchSelectShow()"
               onmouseout="return searchBox.OnSearchSelectHide()"
               alt=""/>
          <input type="text" id="MSearchField" value="Search" accesskey="S"
               onfocus="searchBox.OnSearchFieldFocus(true)" 
               onblur="searchBox.OnSearchFieldFocus(false)" 
               onkeyup="searchBox.OnSearchFieldChange(event)"/>
          </span><span class="right">
            <a id="MSearchClose" href="javascript:searchBox.CloseResultsWindow()"><img id="MSearchCloseImg" border="0" src="search/close.png" alt=""/></a>
          </span>
        </div>
      </li>
    </ul>
  </div>
  <div id="navrow2" class="tabs2">
    <ul class="tablist">
      <li><a href="annotated.html"><span>Class&#160;List</span></a></li>
      <li><a href="classes.html"><span>Class&#160;Index</span></a></li>
      <li><a href="inherits.html"><span>Class&#160;Hierarchy</span></a></li>
      <li><a href="functions.html"><span>Class&#160;Members</span></a></li>
    </ul>
  </div>
<!-- window showing the filter options -->
<div id="MSearchSelectWindow"
     onmouseover="return searchBox.OnSearchSelectShow()"
     onmouseout="return searchBox.OnSearchSelectHide()"
     onkeydown="return searchBox.OnSearchSelectKey(event)">
<a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(0)"><span class="SelectionMark">&#160;</span>All</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(1)"><span class="SelectionMark">&#160;</span>Classes</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(2)"><span class="SelectionMark">&#160;</span>Namespaces</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(3)"><span class="SelectionMark">&#160;</span>Files</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(4)"><span class="SelectionMark">&#160;</span>Functions</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(5)"><span class="SelectionMark">&#160;</span>Variables</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(6)"><span class="SelectionMark">&#160;</span>Typedefs</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(7)"><span class="SelectionMark">&#160;</span>Enumerations</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(8)"><span class="SelectionMark">&#160;</span>Enumerator</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(9)"><span class="SelectionMark">&#160;</span>Friends</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(10)"><span class="SelectionMark">&#160;</span>Macros</a></div>

<!-- iframe showing the search results (closed by default) -->
<div id="MSearchResultsWindow">
<iframe src="javascript:void(0)" frameborder="0" 
        name="MSearchResults" id="MSearchResults">
</iframe>
</div>

</div><!-- top -->
<div class="header">
  <div class="summary">
<a href="#pub-methods">Public Member Functions</a> &#124;
<a href="#pub-static-methods">Static Public Member Functions</a> &#124;
<a href="#pro-methods">Protected Member Functions</a> &#124;
<a href="#pro-attribs">Protected Attributes</a>  </div>
  <div class="headertitle">
<div class="title">ColoringHeuristic&lt; T, D &gt; Class Template Reference</div>  </div>
</div><!--header-->
<div class="contents">

<p>This class encapsulates a set of algorithms to color a graph.  
 <a href="classColoringHeuristic.html#details">More...</a></p>

<p><code>#include &lt;<a class="el" href="ColoringHeuristic_8h_source.html">ColoringHeuristic.h</a>&gt;</code></p>
<div class="dynheader">
Inheritance diagram for ColoringHeuristic&lt; T, D &gt;:</div>
<div class="dyncontent">
<div class="center"><img src="classColoringHeuristic__inherit__graph.png" border="0" usemap="#ColoringHeuristic_3_01T_00_01D_01_4_inherit__map" alt="Inheritance graph"/></div>
<map name="ColoringHeuristic_3_01T_00_01D_01_4_inherit__map" id="ColoringHeuristic_3_01T_00_01D_01_4_inherit__map">
<area shape="rect" id="node3" href="classDsatur.html" title="Dsatur\&lt; T, D \&gt;" alt="" coords="5,101,115,131"/><area shape="rect" id="node5" href="classGreedy.html" title="Greedy\&lt; T, D \&gt;" alt="" coords="139,101,253,131"/><area shape="rect" id="node7" href="classMCR.html" title="MCR\&lt; T, D \&gt;" alt="" coords="277,101,379,131"/></map>
<center><span class="legend">[<a href="graph_legend.html">legend</a>]</span></center></div>
<div class="dynheader">
Collaboration diagram for ColoringHeuristic&lt; T, D &gt;:</div>
<div class="dyncontent">
<div class="center"><img src="classColoringHeuristic__coll__graph.png" border="0" usemap="#ColoringHeuristic_3_01T_00_01D_01_4_coll__map" alt="Collaboration graph"/></div>
<map name="ColoringHeuristic_3_01T_00_01D_01_4_coll__map" id="ColoringHeuristic_3_01T_00_01D_01_4_coll__map">
<area shape="rect" id="node2" href="classFactory.html" title="Factory\&lt; D\&lt; T \&gt; \&gt;" alt="" coords="5,5,136,35"/></map>
<center><span class="legend">[<a href="graph_legend.html">legend</a>]</span></center></div>

<p><a href="classColoringHeuristic-members.html">List of all members.</a></p>
<table class="memberdecls">
<tr class="heading"><td colspan="2"><h2><a name="pub-methods"></a>
Public Member Functions</h2></td></tr>
<tr class="memitem:a7e73234d994a1af4002a87354fb68b1f"><td class="memItemLeft" align="right" valign="top">virtual&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="classColoringHeuristic.html#a7e73234d994a1af4002a87354fb68b1f">~ColoringHeuristic</a> ()</td></tr>
<tr class="memitem:a043dfbbdcaf49f350254e1738de34f82"><td class="memItemLeft" align="right" valign="top">long&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="classColoringHeuristic.html#a043dfbbdcaf49f350254e1738de34f82">run</a> (<a class="el" href="classGraph.html">Graph</a>&lt; D&lt; T &gt; &gt; *g, long *res, long *R, long r)=0</td></tr>
</table><table class="memberdecls">
<tr class="heading"><td colspan="2"><h2><a name="pub-static-methods"></a>
Static Public Member Functions</h2></td></tr>
<tr class="memitem:aa54345bb1fc4a68dd9b135bdb2ecb098"><td class="memItemLeft" align="right" valign="top">static long&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="classColoringHeuristic.html#aa54345bb1fc4a68dd9b135bdb2ecb098">bucketSort</a> (long *color, long cmin, long cmax, long *R, long r)</td></tr>
<tr class="memitem:a7bfb89fa3681e587f3b3f52e5c8183b1"><td class="memItemLeft" align="right" valign="top">static <a class="el" href="classColoringHeuristic.html">ColoringHeuristic</a>&lt; T, D &gt; *&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="classColoringHeuristic.html#a7bfb89fa3681e587f3b3f52e5c8183b1">greedy</a> (long <a class="el" href="classColoringHeuristic.html#af0cb59214cd56b3cdb522d0cc4981273">n</a>, <a class="el" href="classFactory.html">Factory</a>&lt; D &gt; *<a class="el" href="classColoringHeuristic.html#a40cd35433cef882c6d01ba41ba8bb324">factory</a>)</td></tr>
<tr class="memdesc:a7bfb89fa3681e587f3b3f52e5c8183b1"><td class="mdescLeft">&#160;</td><td class="mdescRight">Made a greedy coloring of the subgraph induced by the vertexes in R, with the order that they appear in R.  <a href="#a7bfb89fa3681e587f3b3f52e5c8183b1"></a><br/></td></tr>
<tr class="memitem:a449990b4b90c04a0ba4d0cf55f7f9280"><td class="memItemLeft" align="right" valign="top">static <a class="el" href="classColoringHeuristic.html">ColoringHeuristic</a>&lt; T, D &gt; *&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="classColoringHeuristic.html#a449990b4b90c04a0ba4d0cf55f7f9280">dsatur</a> (long <a class="el" href="classColoringHeuristic.html#af0cb59214cd56b3cdb522d0cc4981273">n</a>, <a class="el" href="classFactory.html">Factory</a>&lt; D &gt; *<a class="el" href="classColoringHeuristic.html#a40cd35433cef882c6d01ba41ba8bb324">factory</a>)</td></tr>
<tr class="memdesc:a449990b4b90c04a0ba4d0cf55f7f9280"><td class="mdescLeft">&#160;</td><td class="mdescRight">Determines a greedy coloring of the subgraph induced by the specified vertices using the <a class="el" href="classDsatur.html">Dsatur</a> algorithm.  <a href="#a449990b4b90c04a0ba4d0cf55f7f9280"></a><br/></td></tr>
<tr class="memitem:a3daa607fd5e566bb6f9b7317aec0120c"><td class="memItemLeft" align="right" valign="top">static <a class="el" href="classColoringHeuristic.html">ColoringHeuristic</a>&lt; T, D &gt; *&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="classColoringHeuristic.html#a3daa607fd5e566bb6f9b7317aec0120c">mcr</a> (long <a class="el" href="classColoringHeuristic.html#af0cb59214cd56b3cdb522d0cc4981273">n</a>, <a class="el" href="classFactory.html">Factory</a>&lt; D &gt; *<a class="el" href="classColoringHeuristic.html#a40cd35433cef882c6d01ba41ba8bb324">factory</a>)</td></tr>
<tr class="memdesc:a3daa607fd5e566bb6f9b7317aec0120c"><td class="mdescLeft">&#160;</td><td class="mdescRight">Cover the vertexes of the graph according its degree and the degree of its neighbours.  <a href="#a3daa607fd5e566bb6f9b7317aec0120c"></a><br/></td></tr>
<tr class="memitem:a81c3d4609d908cc8a16d1d4cd311b47e"><td class="memItemLeft" align="right" valign="top">static double&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="classColoringHeuristic.html#a81c3d4609d908cc8a16d1d4cd311b47e">FCP2</a> (<a class="el" href="classGraph.html">Graph</a> *g, long k, long **rank)</td></tr>
</table><table class="memberdecls">
<tr class="heading"><td colspan="2"><h2><a name="pro-methods"></a>
Protected Member Functions</h2></td></tr>
<tr class="memitem:aab770ebba9e775828c6d837b05c47852"><td class="memItemLeft" align="right" valign="top">&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="classColoringHeuristic.html#aab770ebba9e775828c6d837b05c47852">ColoringHeuristic</a> (long <a class="el" href="classColoringHeuristic.html#af0cb59214cd56b3cdb522d0cc4981273">n</a>, <a class="el" href="classFactory.html">Factory</a>&lt; D&lt; T &gt; &gt; *f)</td></tr>
<tr class="memdesc:aab770ebba9e775828c6d837b05c47852"><td class="mdescLeft">&#160;</td><td class="mdescRight">Creates a covering algorithm object.  <a href="#aab770ebba9e775828c6d837b05c47852"></a><br/></td></tr>
</table><table class="memberdecls">
<tr class="heading"><td colspan="2"><h2><a name="pro-attribs"></a>
Protected Attributes</h2></td></tr>
<tr class="memitem:af0cb59214cd56b3cdb522d0cc4981273"><td class="memItemLeft" align="right" valign="top">const long&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="classColoringHeuristic.html#af0cb59214cd56b3cdb522d0cc4981273">n</a></td></tr>
<tr class="memdesc:af0cb59214cd56b3cdb522d0cc4981273"><td class="mdescLeft">&#160;</td><td class="mdescRight">max number of elements  <a href="#af0cb59214cd56b3cdb522d0cc4981273"></a><br/></td></tr>
<tr class="memitem:a40cd35433cef882c6d01ba41ba8bb324"><td class="memItemLeft" align="right" valign="top"><a class="el" href="classFactory.html">Factory</a>&lt; D&lt; T &gt; &gt; *&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="classColoringHeuristic.html#a40cd35433cef882c6d01ba41ba8bb324">factory</a></td></tr>
<tr class="memitem:ae4cf7db5667d8d65aa6b7c41ee27ef60"><td class="memItemLeft" align="right" valign="top">D&lt; T &gt; *const&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="classColoringHeuristic.html#ae4cf7db5667d8d65aa6b7c41ee27ef60">bitR</a></td></tr>
<tr class="memitem:a99bba05a6a6c8df2bc7ffb4f1f5aea9b"><td class="memItemLeft" align="right" valign="top">D&lt; T &gt; **const&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="classColoringHeuristic.html#a99bba05a6a6c8df2bc7ffb4f1f5aea9b">colors</a></td></tr>
<tr class="memitem:ad51d1ebb6f77365b5737001d39b62324"><td class="memItemLeft" align="right" valign="top"><a class="el" href="classAndFilter.html">AndFilter</a>&lt; T &gt; *&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="classColoringHeuristic.html#ad51d1ebb6f77365b5737001d39b62324">andFilter</a></td></tr>
<tr class="memitem:a2dce80a62997557dc676eb05565c5379"><td class="memItemLeft" align="right" valign="top">long *&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="classColoringHeuristic.html#a2dce80a62997557dc676eb05565c5379">invR</a></td></tr>
<tr class="memdesc:a2dce80a62997557dc676eb05565c5379"><td class="mdescLeft">&#160;</td><td class="mdescRight">inverse of input mappings  <a href="#a2dce80a62997557dc676eb05565c5379"></a><br/></td></tr>
<tr class="memitem:a3af684edbb71a7a430e05e3e79ec938c"><td class="memItemLeft" align="right" valign="top">D&lt; T &gt; *const&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="classColoringHeuristic.html#a3af684edbb71a7a430e05e3e79ec938c">degR</a></td></tr>
</table>
<hr/><a name="details" id="details"></a><h2>Detailed Description</h2>
<div class="textblock"><h3>template&lt;typename T, template&lt; typename T &gt; class D&gt;<br/>
class ColoringHeuristic&lt; T, D &gt;</h3>

<p>This class encapsulates a set of algorithms to color a graph. </p>
<p>The most basic ones are to color or to determine the connected components of a graph.</p>
<p>A coloring of a graph is a assignment of colors to the vertexes of the graph in such away that if to vertexes are adjacent they have different colors.</p>
<p>The connected components of a graph are a set of graphs such that each vertex and edge belong to only one graph, the union of its vertexes sets and edge sets are the vertex set and the edge set of the initial graph and all the graphs in the set are connected, what means that in each graph there are a path between every pair of vertices.</p>
<dl class="tparams"><dt>Template Parameters:</dt><dd>
  <table class="tparams">
    <tr><td class="paramname">T</td><td>define the bitmap directly addressed sets</td></tr>
  </table>
  </dd>
</dl>
<dl class="section see"><dt>See also:</dt><dd><a class="el" href="classGraph.html">Graph</a> </dd>
<dd>
<a class="el" href="classBitMapDirectlyAddressedSet.html" title="A DirectlyAddressedSet implemented with an array of nodes, each node corresponding to a word of the s...">BitMapDirectlyAddressedSet</a> </dd></dl>
</div><hr/><h2>Constructor &amp; Destructor Documentation</h2>
<a class="anchor" id="aab770ebba9e775828c6d837b05c47852"></a>
<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template&lt;typename T , template&lt; typename T &gt; class D&gt; </div>
<table class="mlabels">
  <tr>
  <td class="mlabels-left">
      <table class="memname">
        <tr>
          <td class="memname"><a class="el" href="classColoringHeuristic.html">ColoringHeuristic</a>&lt; T, D &gt;::<a class="el" href="classColoringHeuristic.html">ColoringHeuristic</a> </td>
          <td>(</td>
          <td class="paramtype">long&#160;</td>
          <td class="paramname"><em>n</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype"><a class="el" href="classFactory.html">Factory</a>&lt; D&lt; T &gt; &gt; *&#160;</td>
          <td class="paramname"><em>f</em>&#160;</td>
        </tr>
        <tr>
          <td></td>
          <td>)</td>
          <td></td><td></td>
        </tr>
      </table>
  </td>
  <td class="mlabels-right">
<span class="mlabels"><span class="mlabel">protected</span></span>  </td>
  </tr>
</table>
</div><div class="memdoc">

<p>Creates a covering algorithm object. </p>
<p>Free list is initialized containing all nodes.</p>
<dl class="params"><dt>Parameters:</dt><dd>
  <table class="params">
    <tr><td class="paramname">n</td><td>size of internal arrays and sets </td></tr>
    <tr><td class="paramname">factory</td><td>a factory to <a class="el" href="classBitMapDirectlyAddressedSet.html" title="A DirectlyAddressedSet implemented with an array of nodes, each node corresponding to a word of the s...">BitMapDirectlyAddressedSet</a> to be used to instantiate the variables. </td></tr>
  </table>
  </dd>
</dl>

</div>
</div>
<a class="anchor" id="a7e73234d994a1af4002a87354fb68b1f"></a>
<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template&lt;typename T , template&lt; typename T &gt; class D&gt; </div>
<table class="mlabels">
  <tr>
  <td class="mlabels-left">
      <table class="memname">
        <tr>
          <td class="memname"><a class="el" href="classColoringHeuristic.html">ColoringHeuristic</a>&lt; T, D &gt;::~<a class="el" href="classColoringHeuristic.html">ColoringHeuristic</a> </td>
          <td>(</td>
          <td class="paramname"></td><td>)</td>
          <td></td>
        </tr>
      </table>
  </td>
  <td class="mlabels-right">
<span class="mlabels"><span class="mlabel">virtual</span></span>  </td>
  </tr>
</table>
</div><div class="memdoc">

</div>
</div>
<hr/><h2>Member Function Documentation</h2>
<a class="anchor" id="aa54345bb1fc4a68dd9b135bdb2ecb098"></a>
<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template&lt;typename T , template&lt; typename T &gt; class D&gt; </div>
<table class="mlabels">
  <tr>
  <td class="mlabels-left">
      <table class="memname">
        <tr>
          <td class="memname">long <a class="el" href="classColoringHeuristic.html">ColoringHeuristic</a>&lt; T, D &gt;::bucketSort </td>
          <td>(</td>
          <td class="paramtype">long *&#160;</td>
          <td class="paramname"><em>color</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype">long&#160;</td>
          <td class="paramname"><em>cmin</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype">long&#160;</td>
          <td class="paramname"><em>cmax</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype">long *&#160;</td>
          <td class="paramname"><em>R</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype">long&#160;</td>
          <td class="paramname"><em>r</em>&#160;</td>
        </tr>
        <tr>
          <td></td>
          <td>)</td>
          <td></td><td></td>
        </tr>
      </table>
  </td>
  <td class="mlabels-right">
<span class="mlabels"><span class="mlabel">inline</span><span class="mlabel">static</span></span>  </td>
  </tr>
</table>
</div><div class="memdoc">

</div>
</div>
<a class="anchor" id="a449990b4b90c04a0ba4d0cf55f7f9280"></a>
<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template&lt;typename T , template&lt; typename T &gt; class D&gt; </div>
<table class="mlabels">
  <tr>
  <td class="mlabels-left">
      <table class="memname">
        <tr>
          <td class="memname"><a class="el" href="classColoringHeuristic.html">ColoringHeuristic</a>&lt; T, D &gt; * <a class="el" href="classColoringHeuristic.html">ColoringHeuristic</a>&lt; T, D &gt;::dsatur </td>
          <td>(</td>
          <td class="paramtype">long&#160;</td>
          <td class="paramname"><em>n</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype"><a class="el" href="classFactory.html">Factory</a>&lt; D &gt; *&#160;</td>
          <td class="paramname"><em>factory</em>&#160;</td>
        </tr>
        <tr>
          <td></td>
          <td>)</td>
          <td></td><td></td>
        </tr>
      </table>
  </td>
  <td class="mlabels-right">
<span class="mlabels"><span class="mlabel">static</span></span>  </td>
  </tr>
</table>
</div><div class="memdoc">

<p>Determines a greedy coloring of the subgraph induced by the specified vertices using the <a class="el" href="classDsatur.html">Dsatur</a> algorithm. </p>
<p>The order used to guide the greedy coloring is specified by a function given as input. The <a class="el" href="classDsatur.html">Dsatur</a> algorithm keeps track of the so called saturation degree of each vertex. The saturation degree of a vertex <code>v</code> is the number of already colored vertices in the neighborhood of <code>v</code>. At each iteration, the uncolored vertex with the largest saturation degree (with the largest degree used to break ties, whenever possible) is chosen to be colored.</p>
<dl class="params"><dt>Parameters:</dt><dd>
  <table class="params">
    <tr><td class="paramname">n</td><td>size of internal arrays and sets </td></tr>
    <tr><td class="paramname">factory</td><td>a factory to <a class="el" href="classBitMapDirectlyAddressedSet.html" title="A DirectlyAddressedSet implemented with an array of nodes, each node corresponding to a word of the s...">BitMapDirectlyAddressedSet</a> to be used to instantiate the variables.</td></tr>
  </table>
  </dd>
</dl>
<dl class="section return"><dt>Returns:</dt><dd>the covering algorithm object created</dd></dl>
<dl class="section see"><dt>See also:</dt><dd><a href="http://www.math.tu-clausthal.de/Arbeitsgruppen/Diskrete-Optimierung/publications/2002/gca.pdf">http://www.math.tu-clausthal.de/Arbeitsgruppen/Diskrete-Optimierung/publications/2002/gca.pdf</a> </dd></dl>

</div>
</div>
<a class="anchor" id="a81c3d4609d908cc8a16d1d4cd311b47e"></a>
<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template&lt;typename T, template&lt; typename T &gt; class D&gt; </div>
<table class="mlabels">
  <tr>
  <td class="mlabels-left">
      <table class="memname">
        <tr>
          <td class="memname">static double <a class="el" href="classColoringHeuristic.html">ColoringHeuristic</a>&lt; T, D &gt;::FCP2 </td>
          <td>(</td>
          <td class="paramtype"><a class="el" href="classGraph.html">Graph</a> *&#160;</td>
          <td class="paramname"><em>g</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype">long&#160;</td>
          <td class="paramname"><em>k</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype">long **&#160;</td>
          <td class="paramname"><em>rank</em>&#160;</td>
        </tr>
        <tr>
          <td></td>
          <td>)</td>
          <td></td><td></td>
        </tr>
      </table>
  </td>
  <td class="mlabels-right">
<span class="mlabels"><span class="mlabel">static</span></span>  </td>
  </tr>
</table>
</div><div class="memdoc">
<dl class="params"><dt>Parameters:</dt><dd>
  <table class="params">
    <tr><td class="paramname">g</td><td></td></tr>
    <tr><td class="paramname">k</td><td></td></tr>
    <tr><td class="paramname">rank</td><td></td></tr>
  </table>
  </dd>
</dl>
<dl class="section return"><dt>Returns:</dt><dd></dd></dl>

</div>
</div>
<a class="anchor" id="a7bfb89fa3681e587f3b3f52e5c8183b1"></a>
<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template&lt;typename T , template&lt; typename T &gt; class D&gt; </div>
<table class="mlabels">
  <tr>
  <td class="mlabels-left">
      <table class="memname">
        <tr>
          <td class="memname"><a class="el" href="classColoringHeuristic.html">ColoringHeuristic</a>&lt; T, D &gt; * <a class="el" href="classColoringHeuristic.html">ColoringHeuristic</a>&lt; T, D &gt;::greedy </td>
          <td>(</td>
          <td class="paramtype">long&#160;</td>
          <td class="paramname"><em>n</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype"><a class="el" href="classFactory.html">Factory</a>&lt; D &gt; *&#160;</td>
          <td class="paramname"><em>factory</em>&#160;</td>
        </tr>
        <tr>
          <td></td>
          <td>)</td>
          <td></td><td></td>
        </tr>
      </table>
  </td>
  <td class="mlabels-right">
<span class="mlabels"><span class="mlabel">static</span></span>  </td>
  </tr>
</table>
</div><div class="memdoc">

<p>Made a greedy coloring of the subgraph induced by the vertexes in R, with the order that they appear in R. </p>
<p>Made a coloring, greedy coloring of the subgraph induced by the vertexes in R. The order used to built suc coloring is the same order that the vertexes appear in R. The algorithm visit each element in R, in order, and look for the smallest color not used in one of its neighbours to color it. If there is not such color a new color will be add to the set of possible colors.</p>
<dl class="params"><dt>Parameters:</dt><dd>
  <table class="params">
    <tr><td class="paramname">n</td><td>size of internal arrays and sets </td></tr>
    <tr><td class="paramname">factory</td><td>a factory to <a class="el" href="classBitMapDirectlyAddressedSet.html" title="A DirectlyAddressedSet implemented with an array of nodes, each node corresponding to a word of the s...">BitMapDirectlyAddressedSet</a> to be used to instantiate the variables.</td></tr>
  </table>
  </dd>
</dl>
<dl class="section return"><dt>Returns:</dt><dd>the covering algorithm object created </dd></dl>

</div>
</div>
<a class="anchor" id="a3daa607fd5e566bb6f9b7317aec0120c"></a>
<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template&lt;typename T , template&lt; typename T &gt; class D&gt; </div>
<table class="mlabels">
  <tr>
  <td class="mlabels-left">
      <table class="memname">
        <tr>
          <td class="memname"><a class="el" href="classColoringHeuristic.html">ColoringHeuristic</a>&lt; T, D &gt; * <a class="el" href="classColoringHeuristic.html">ColoringHeuristic</a>&lt; T, D &gt;::mcr </td>
          <td>(</td>
          <td class="paramtype">long&#160;</td>
          <td class="paramname"><em>n</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype"><a class="el" href="classFactory.html">Factory</a>&lt; D &gt; *&#160;</td>
          <td class="paramname"><em>factory</em>&#160;</td>
        </tr>
        <tr>
          <td></td>
          <td>)</td>
          <td></td><td></td>
        </tr>
      </table>
  </td>
  <td class="mlabels-right">
<span class="mlabels"><span class="mlabel">static</span></span>  </td>
  </tr>
</table>
</div><div class="memdoc">

<p>Cover the vertexes of the graph according its degree and the degree of its neighbours. </p>
<p>Return an order to the vertexes in R, according the degrees in the subgraph induced for it. More clearly, if cover[i] = j it means that in the graph induced by the vertexes R[k] that has cover[k] &lt; j, R[i] is a vertex with minimum degree.</p>
<p>The integer value returned by this function is the biggest k such that k is the minimum degree in the subgraph induced by R[0] .... R[i] for all i &lt; r.</p>
<dl class="params"><dt>Parameters:</dt><dd>
  <table class="params">
    <tr><td class="paramname">g</td><td>the graph</td></tr>
    <tr><td class="paramname">cover</td><td>represent the order over the vertexes of g, the position i of this vector indicate the position of the vertex i in the order.</td></tr>
    <tr><td class="paramname">R</td><td>a vector representing the vertexes to be colored and the order to be used to color then.</td></tr>
    <tr><td class="paramname">r</td><td>the number of vertexes in the subgraph.</td></tr>
    <tr><td class="paramname">factory</td><td>a factory to OrderedSet to be used to instance the variables.</td></tr>
  </table>
  </dd>
</dl>
<dl class="section return"><dt>Returns:</dt><dd>the maximum mininum degree in the subgraph. </dd></dl>

</div>
</div>
<a class="anchor" id="a043dfbbdcaf49f350254e1738de34f82"></a>
<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template&lt;typename T, template&lt; typename T &gt; class D&gt; </div>
<table class="mlabels">
  <tr>
  <td class="mlabels-left">
      <table class="memname">
        <tr>
          <td class="memname">long <a class="el" href="classColoringHeuristic.html">ColoringHeuristic</a>&lt; T, D &gt;::run </td>
          <td>(</td>
          <td class="paramtype"><a class="el" href="classGraph.html">Graph</a>&lt; D&lt; T &gt; &gt; *&#160;</td>
          <td class="paramname"><em>g</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype">long *&#160;</td>
          <td class="paramname"><em>res</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype">long *&#160;</td>
          <td class="paramname"><em>R</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype">long&#160;</td>
          <td class="paramname"><em>r</em>&#160;</td>
        </tr>
        <tr>
          <td></td>
          <td>)</td>
          <td></td><td></td>
        </tr>
      </table>
  </td>
  <td class="mlabels-right">
<span class="mlabels"><span class="mlabel">pure virtual</span></span>  </td>
  </tr>
</table>
</div><div class="memdoc">
<dl class="params"><dt>Parameters:</dt><dd>
  <table class="params">
    <tr><td class="paramname">g</td><td>the input graph </td></tr>
    <tr><td class="paramname">res</td><td>the vector in which the colors are returned: the position <code>i</code> in this vector indicates the color of the vertex <code>R</code>[i] in the greedy coloring of the subgraph induced by <code>R</code>. </td></tr>
    <tr><td class="paramname">R</td><td>a vector representing the verticees to be colored and the order to be used to color them. </td></tr>
    <tr><td class="paramname">r</td><td>the number of verticees in the subgraph.</td></tr>
  </table>
  </dd>
</dl>
<dl class="section return"><dt>Returns:</dt><dd>the number of colors used in the greedy coloring of the subgraph induced by <code>R</code> returned in <code>cover</code> </dd></dl>

<p>Implemented in <a class="el" href="classMCR.html#a36b25e017c31dc53258c0ec36191cb06">MCR&lt; T, D &gt;</a>, <a class="el" href="classDsatur.html#af30bebb51dc3aa571543fdb1d5507c10">Dsatur&lt; T, D &gt;</a>, and <a class="el" href="classGreedy.html#ae0d2d21ed0e4a01944051e79dfc75a1a">Greedy&lt; T, D &gt;</a>.</p>

</div>
</div>
<hr/><h2>Member Data Documentation</h2>
<a class="anchor" id="ad51d1ebb6f77365b5737001d39b62324"></a>
<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template&lt;typename T, template&lt; typename T &gt; class D&gt; </div>
<table class="mlabels">
  <tr>
  <td class="mlabels-left">
      <table class="memname">
        <tr>
          <td class="memname"><a class="el" href="classAndFilter.html">AndFilter</a>&lt;T&gt;* <a class="el" href="classColoringHeuristic.html">ColoringHeuristic</a>&lt; T, D &gt;::andFilter</td>
        </tr>
      </table>
  </td>
  <td class="mlabels-right">
<span class="mlabels"><span class="mlabel">protected</span></span>  </td>
  </tr>
</table>
</div><div class="memdoc">

</div>
</div>
<a class="anchor" id="ae4cf7db5667d8d65aa6b7c41ee27ef60"></a>
<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template&lt;typename T, template&lt; typename T &gt; class D&gt; </div>
<table class="mlabels">
  <tr>
  <td class="mlabels-left">
      <table class="memname">
        <tr>
          <td class="memname">D&lt;T&gt;* const <a class="el" href="classColoringHeuristic.html">ColoringHeuristic</a>&lt; T, D &gt;::bitR</td>
        </tr>
      </table>
  </td>
  <td class="mlabels-right">
<span class="mlabels"><span class="mlabel">protected</span></span>  </td>
  </tr>
</table>
</div><div class="memdoc">

</div>
</div>
<a class="anchor" id="a99bba05a6a6c8df2bc7ffb4f1f5aea9b"></a>
<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template&lt;typename T, template&lt; typename T &gt; class D&gt; </div>
<table class="mlabels">
  <tr>
  <td class="mlabels-left">
      <table class="memname">
        <tr>
          <td class="memname">D&lt;T&gt;** const <a class="el" href="classColoringHeuristic.html">ColoringHeuristic</a>&lt; T, D &gt;::colors</td>
        </tr>
      </table>
  </td>
  <td class="mlabels-right">
<span class="mlabels"><span class="mlabel">protected</span></span>  </td>
  </tr>
</table>
</div><div class="memdoc">

</div>
</div>
<a class="anchor" id="a3af684edbb71a7a430e05e3e79ec938c"></a>
<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template&lt;typename T, template&lt; typename T &gt; class D&gt; </div>
<table class="mlabels">
  <tr>
  <td class="mlabels-left">
      <table class="memname">
        <tr>
          <td class="memname">D&lt;T&gt;* const <a class="el" href="classColoringHeuristic.html">ColoringHeuristic</a>&lt; T, D &gt;::degR</td>
        </tr>
      </table>
  </td>
  <td class="mlabels-right">
<span class="mlabels"><span class="mlabel">protected</span></span>  </td>
  </tr>
</table>
</div><div class="memdoc">

</div>
</div>
<a class="anchor" id="a40cd35433cef882c6d01ba41ba8bb324"></a>
<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template&lt;typename T, template&lt; typename T &gt; class D&gt; </div>
<table class="mlabels">
  <tr>
  <td class="mlabels-left">
      <table class="memname">
        <tr>
          <td class="memname"><a class="el" href="classFactory.html">Factory</a>&lt;D&lt;T&gt; &gt;* <a class="el" href="classColoringHeuristic.html">ColoringHeuristic</a>&lt; T, D &gt;::factory</td>
        </tr>
      </table>
  </td>
  <td class="mlabels-right">
<span class="mlabels"><span class="mlabel">protected</span></span>  </td>
  </tr>
</table>
</div><div class="memdoc">

</div>
</div>
<a class="anchor" id="a2dce80a62997557dc676eb05565c5379"></a>
<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template&lt;typename T, template&lt; typename T &gt; class D&gt; </div>
<table class="mlabels">
  <tr>
  <td class="mlabels-left">
      <table class="memname">
        <tr>
          <td class="memname">long* <a class="el" href="classColoringHeuristic.html">ColoringHeuristic</a>&lt; T, D &gt;::invR</td>
        </tr>
      </table>
  </td>
  <td class="mlabels-right">
<span class="mlabels"><span class="mlabel">protected</span></span>  </td>
  </tr>
</table>
</div><div class="memdoc">

<p>inverse of input mappings </p>

</div>
</div>
<a class="anchor" id="af0cb59214cd56b3cdb522d0cc4981273"></a>
<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template&lt;typename T, template&lt; typename T &gt; class D&gt; </div>
<table class="mlabels">
  <tr>
  <td class="mlabels-left">
      <table class="memname">
        <tr>
          <td class="memname">const long <a class="el" href="classColoringHeuristic.html">ColoringHeuristic</a>&lt; T, D &gt;::n</td>
        </tr>
      </table>
  </td>
  <td class="mlabels-right">
<span class="mlabels"><span class="mlabel">protected</span></span>  </td>
  </tr>
</table>
</div><div class="memdoc">

<p>max number of elements </p>

</div>
</div>
<hr/>The documentation for this class was generated from the following file:<ul>
<li>graphs/<a class="el" href="ColoringHeuristic_8h_source.html">ColoringHeuristic.h</a></li>
</ul>
</div><!-- contents -->
<!-- start footer part -->
<hr class="footer"/><address class="footer"><small>
Generated on Mon Nov 26 2012 17:06:46 for Data Structures for Sets and Graphs by &#160;<a href="http://www.doxygen.org/index.html">
<img class="footer" src="doxygen.png" alt="doxygen"/>
</a> 1.8.1.1
</small></address>
</body>
</html>
